package com.LeeCode;

/**
 * 跳跃游戏Ⅱ
 */

public class Code045 {
    public static void main(String[] args) {
        int[] nums = {4, 1, 1, 3, 1, 1, 1};
        System.out.println(new Code045().jump(nums));
    }

    public int jump(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return 0;
        }
        int[] aux = new int[len];
        int maxIndex;
        for (int i = 0; i < len; i++) {
            maxIndex = Math.min(len - 1, i + nums[i]);
            for (int j = i + 1; j <= maxIndex; j++) {
                if (aux[j] == 0) {
                    aux[j] = aux[i] + 1;
                }
            }
            if (maxIndex == len - 1) {
                break;
            }
        }
        return aux[len - 1];
    }

    public int jump1(int[] nums) {
        int max_reach = 0;
        //记录当前这次起跳的边界下标,第一次只能从0开始起跳，0就是第一次跳跃的边界
        int boundary = 0;
        int steps = 0;

        for (int i = 0; i < nums.length - 1; ++i) {
            //更新起跳区间 [当前位置i,boundry] 能够到达的最远下标
            max_reach = Math.max(max_reach, nums[i] + i);
            //如果能到达末尾，提前退出循环
            if (max_reach >= nums.length - 1) {
                return steps + 1;
            }
            //如果到达了边界，就一定要跳了，下一跳的边界下标就是之前统计的最优maxPosition
            if (i == boundary) {
                //下一次起跳的边界
                boundary = max_reach;
                steps++;
            }
        }
        return steps;
    }
}
